CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)

MEXanized Array

分类讨论，一开始以为不能有重复，花了很多时间。（菜）

public static void solve() {
    int n = io.nextInt(), k = io.nextInt(), x = io.nextInt();
    if (n < k || x < k - 1) io.println(-1);
    else io.println((k - 1) * k / 2 + (n - k) * (x == k ? k - 1 : x));
}

Friendly Arrays

又看错题了，其实是道很简单的题。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int a = 0;
    for (int i = 0; i < n; i++) {
        a ^= io.nextInt();
    }
    int b = 0;
    for (int i = 0; i < m; i++) {
        b |= io.nextInt();
    }
    int min = a, max = a;
    if (n % 2 == 0) {
        min = a ^ (a & b);
    } else {
        max = a | b;
    }
    io.println(min + " " + max);
}

Colorful Table

一个数可以向外扩展到大于等于它的的数的位置，我们可以按 \(k\) 的大小记录左右端点，然后按照从大到小遍历，来扩展边界，最后计算答案。注意，排除不在数组中的数。

public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    boolean[] mark = new boolean[k];
    int[] l = new int[k], r = new int[k];
    Arrays.fill(l, n);
    Arrays.fill(r, -1);
    for (int i = 0; i < n; i++) {
        int a = io.nextInt() - 1;
        mark[a] = true;
        l[a] = Math.min(l[a], i);
        r[a] = i;
    }
    for (int i = k - 2; i >= 0; i--) {
        l[i] = Math.min(l[i], l[i + 1]);
        r[i] = Math.max(r[i], r[i + 1]);
    }
    for (int i = 0; i < k; i++) {
        if (!mark[i]) io.print(0 + " ");
        else io.print(2 * (r[i] - l[i] + 1) + " ");
    }
    io.println();
}

Prefix Purchase

又又犯蠢了，题目都没读明白。如果右边有更小的数，那么肯定选更小的数是更优的，可以从右向左遍历，将右边的最小值传递到当前位置。然后就是依次处理每个位置，细节见代码。

void solve() {
    int n;
    cin >> n;
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    int k;
    cin >> k;
    for (int i = n - 2; i >= 0; i--) {
        c[i] = min(c[i], c[i + 1]);
    }
    int m = k;
    for (int i = 0; i < n; i++) {
        int x = i == 0 ? c[i] : c[i] - c[i - 1];
        if (x != 0) m = min(m, k / x);
        k -= x * m;
        cout << m << " \n"[i == n - 1];
    }
}